package com.zofer.study.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description 获取树最大宽度
 * 借用队列，遍历完当前层的下一层的树所有节点放入队列中,即队列中的节点数就是该层的树宽度
 * @date: 2020/10/15 11:22
 */
public class TreeWidth {

    public static void main(String[] args) {
        // 第五层
        TreeNode left211 = new TreeNode(0);
        TreeNode right211 = new TreeNode(0);

        // 第四层
        TreeNode left21 = new TreeNode(0);
        left21.left = left211;
        left21.right = right211;

        // 第三层
        TreeNode left111 = new TreeNode(0);
        left111.left = left21;

        TreeNode right111 = new TreeNode(0);

        TreeNode left121 = new TreeNode(0);
        TreeNode right121 = new TreeNode(0);

        // 第二层
        TreeNode left11 = new TreeNode(0);
        left11.left = left111;
        left11.right = right111;

        TreeNode right12 = new TreeNode(0);
        right12.left = left121;
        right12.right = right121;

        // 第一层
        TreeNode root = new TreeNode(0);
        root.left = left11;
        root.right = right12;

        System.out.println("======================");

        //树最大宽度
        int treeMaxWidth = getTreeMaxWidth(root);
        System.out.println("树最大宽度:"+treeMaxWidth);

    }


    /**
     * 获取树最大宽度
     */
    public static int getTreeMaxWidth(TreeNode treeNode){
        if (treeNode == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int treeMaxWidth = 1;
        queue.add(treeNode);

        while (true){
            //当前层节点个数
            int size = queue.size();
            if (size == 0){
                break;
            }
            while (size > 0){
                TreeNode node = queue.poll();
                size--;
                if (node.left != null){
                    queue.add(node.left);
                }

                if (node.right != null){
                    queue.add(node.right);
                }
            }
            treeMaxWidth = Math.max(treeMaxWidth,queue.size());
        }
        return treeMaxWidth;
    }



}
